#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <algorithm>
#include <limits>
#include <time.h>
using namespace std;

#define Max 50
#define RAND_MAX 100

void RandomGenerateMaTrix(int a[Max][Max], int n);
void PrintMatrix(int a[Max][Max], int n);
int random_in_range (unsigned int min, unsigned int max);


int random_in_range (unsigned int min, unsigned int max)
{
  //Randomize
	int base_random = rand(); /* in [0, RAND_MAX] */
	if (RAND_MAX == base_random) return random_in_range(min, max);
  /* now guaranteed to be in [0, RAND_MAX) */
	int range       = max - min,
      remainder   = RAND_MAX % range,
      bucket      = RAND_MAX / range;
  /* There are range buckets, plus one smaller interval
     within remainder of RAND_MAX */
  if (base_random < RAND_MAX - remainder) {
    return min + base_random/bucket;
  } else {
    return random_in_range (min, max);
  }
}

void RandomGenerateMatrix(int a[Max][Max], int n)
{
	for(int i = 0; i < n; i++)
	{
		for	(int j = 0; j < n; j++)
		{
			if(i==j)
			{
				a[i][j] = 0;	
			}
			else
			
			a[i][j] = random_in_range(1,10);	
		}
	}
}

void PrintMatrix(int a[Max][Max], int n)
{
	printf("\n");
	for(int i = 0; i < n; i++)
	{
		for	(int j = 0; j < n; j++)
		{
			printf("  %d",a[i][j]);	
		}
		printf("\n\n");
	}
}

int main () {
	
	int TotalCost = 0;//Luu lai tong chi phi cua mot chu trinh
	int LastCity;//Luu lai thanh pho cuoi cung duoc ghe tham, truoc khi tro ve thanh pho 1
	int MaTrixForCitiesDistances[Max][Max]; //Ma tran lu lai chi phi duong di giua cac thanh php	
	int NumberOfCity = 4; //Tong so thanh pho 	
	int TravelPath[Max];  //Luu mot chu trinh travel
	int MinCost = std::numeric_limits<int>::max(); //Ket qua: chi phi thap nhat
	int cost = 0;
	int city1 = 0;
	int city2 = 0;
	//printf("%d\n",MinCost);
	//printf("\n");
	for(int id = 2; id<= 15; id++)
	{
		NumberOfCity = id;
		MinCost = std::numeric_limits<int>::max();
		int BestPath[Max];
		RandomGenerateMatrix(MaTrixForCitiesDistances, NumberOfCity);
		//PrintMatrix(MaTrixForCitiesDistances, NumberOfCity);
		//printf("Path: 1  ");
		//Ta co dinh thanh pho ban dau
		//Va tao hoan vi cho (n-1) thanh pho con lai
		for(int i = 0; i <= NumberOfCity-2; i++)
		{
			TravelPath[i] = i + 2;
			//printf("%d  ", i + 2);
		}

		//
		//Vong lap while de khoi tao hoan vi cua cac thanh pho
		clock_t start = clock();
		do
		{
			//Moi lan lap, tao ra mot hoan vi cua (n-1) thanh pho
			TotalCost = 0;

			//printf("\n");
			//printf("1 ");
			//printf("1-");

			//Tinh chi phi tu thanh pho 1 thanh pho tiep theo
			cost = MaTrixForCitiesDistances[0][TravelPath[0]-1];
			TotalCost += cost;
			//

			//printf("{%d}", cost);
			
			//Tinh chi phi cua (n-1) thanh pho con lai
			for(int i = 0; i <= NumberOfCity-3; i++)
			{				
				
				//printf("%d ", TravelPath[i]); 
				cost = MaTrixForCitiesDistances[ TravelPath[i] - 1][TravelPath[i+1] - 1];				
				//printf("-%d-", TravelPath[i]);
				//printf("{%d}", cost);
				TotalCost += cost;
			}
			//printf("1 ");
			//printf("-%d-",TravelPath[NumberOfCity-2]);
			cost = MaTrixForCitiesDistances[TravelPath[NumberOfCity-2] - 1][0];
			//printf("{%d}-1", cost);
			TotalCost+=cost;
			//printf(" ==> %d", TotalCost);

			if(TotalCost < MinCost)
			{
				MinCost = TotalCost;
				for(int i = 0; i <= NumberOfCity-2; i++)
				{
					BestPath[i] = TravelPath[i];
				}
			}
  		} while ( next_permutation (TravelPath,TravelPath+NumberOfCity-1));              
  		//} while ( next_permutation (myints,myints+n) );

		printf("\nNumber of Cities: %d", NumberOfCity);
		printf("\nMin Cost: %d", MinCost);

		printf("\n\tBest Path:");
		printf("  1");
		for(int i = 0; i <= NumberOfCity-2; i++)
		{
			printf("  %d", BestPath[i]);
		}
		printf("  1\n");
		printf("     Time elapsed: %f\n\n", ((double)clock() - start) / CLOCKS_PER_SEC);
		getch();
	}
	getch();
  	return 0;                                                                         
}